public class Test {
    /*
    将有序数组转换为二叉搜索树
    class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length);
    }

    TreeNode dfs(int[] nums, int left, int right) {
        if (left == right)
            return null;

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, left, mid);
        root.right = dfs(nums, mid + 1, right);

        return root;
    }
}
     */

    /*
    class Solution {
    public boolean checkValidString(String s) {

        // 记录左括号
        Stack<Integer> left = new Stack<>();
        // 记录*号
        Stack<Integer> star = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            // 让( *进栈
            char ch = s.charAt(i);
            if (ch == '(') {
                left.push(i);
            }
            if (ch == '*') {
                star.push(i);
            }
            // 遇到)
            if (ch == ')') {
                // 先出left
                if (!left.isEmpty()) {
                    left.pop();
                } else if (!star.isEmpty()) {
                    star.pop();
                } else {
                    return false;
                }
            }
        }
        // 判断大小
        if (left.size() > star.size()) {
            return false;
        } else {
            // left 不为空 star不为空 看看是否存在left的下标大于*的下标 *( 这种情况
            while (!left.isEmpty() && !star.isEmpty()) {
                int top1 = left.pop();
                int top2 = star.pop();
                if (top1 > top2) {
                    return false;
                }
            }

        }
        return true;
    }
}
     */
    /*
    移掉 K 位数字
    class Solution {
    public String removeKdigits(String num, int k) {
        if(num.length() == k) {
            return "0";
        }
        //保留最小的字符 最后再反转
        Deque<Character> s = new LinkedList<>();
        for(int i = 0 ;i < num.length(); i++) {
            char ch = num.charAt(i);
            //移除元素
            // 1 0 5 5 4 3    保留俩位 0 3
            while(!s.isEmpty() && ch < s.getLast() && k >0) {
                s.removeLast();
                k--;
            }
            s.addLast(ch);
        }
        //
        while(!s.isEmpty() && k != 0) {
            k--;
            s.removeLast();
        }
        //移除前导0
        while(!s.isEmpty() && s.getFirst() == '0') {
            s.removeFirst();
            if(s.isEmpty()) return "0";
        }
        //取出元素
        StringBuffer sb = new StringBuffer();
        while(!s.isEmpty()) {
            sb.append(s.getFirst());
            s.removeFirst();
        }
        return sb.toString();


    }
}
     */
}
